package algorithm.migong;

/**
 * @ClassName : data_structure.migong.MigongTest
 * @Description : 类描述
 * Created by cyd on 2021-02-13 17:47:47
 */
public class MiGongTest {
    public static void main(String[] args) {
        int[][] map = new int[8][7];
        // 设置迷宫边界
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        // 设置挡板
        map[3][1] = 1;
        map[3][2] = 1;

        // 按照下、右、上、左 的策略探寻出路
        oneStep(map, 1, 1);

        // 显示迷宫和轨迹
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + "  ");
            }
            System.out.println();
        }

    }

    /**
     * @Author: cyd
     * @Description: 按照下、右、上、左 的策略探寻出路，如果有路，当前位置置为2，如果判定是死路，当前位置置为3
     * @DateTime: 2021/2/13
     * @Params map：代表地图的二维数组  i：探索起始位置的纵坐标  j：探索起始位置的横坐标
     * @Return 如果返回true表示走得通，如果返回false表示走不通
     */
    private static boolean oneStep(int[][] map, int i, int j) {
        if (map[6][5] == 2) {
            return true;
        }

        if (map[i][j] == 0) {
            map[i][j] = 2;
            // 假定当前位置走得通，判断下一步是否也走得通
            if (oneStep(map, i + 1, j)) {
                return true;
            } else if (oneStep(map, i, j + 1)) {
                return true;
            } else if (oneStep(map, i - 1, j)) {
                return true;
            } else if (oneStep(map, i, j - 1)) {
                return true;
            } else {
                // 遇到死路，返回上一层，并在此位置打上标记3
                map[i][j] = 3;
                return false;
            }
        } else {
            // 这个位置被走过了，不再重复走，回溯
            return false;
        }
    }
}
